package com.kevinkk.tree;

/**
 * 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
 */

public class ConstructBinaryTreeFromInorderAndPostorderTraversal {
    class Solution {
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            int len = postorder.length;
            if (len == 0) return null;
            // 后序序列最后一个是根节点
            int val = postorder[len - 1], index = 0;
            TreeNode root = new TreeNode(val);
            // 从中序序列中找到根节点
            while (index < len) {
                if (inorder[index] == val) break;
                index++;
            }

            int[] inorderLeft = new int[index];
            int[] inorderRight = new int[len - index - 1];
            int[] postorderLeft = new int[index];
            int[] postorderRight = new int[len - index - 1];

            System.arraycopy(inorder, 0, inorderLeft, 0, index);
            System.arraycopy(inorder, index + 1, inorderRight, 0, len - index - 1);
            System.arraycopy(postorder, 0, postorderLeft, 0, index);
            System.arraycopy(postorder, index, postorderRight, 0, len - index - 1);

            root.left = buildTree(inorderLeft, postorderLeft);
            root.right = buildTree(inorderRight, postorderRight);
            return root;
        }
    }
}
